区间dp

一.概念

对于一段区间求最优解,且该区间可以分为几个小区间的最优解合并(最优子结构)。

二.基本思路

阅读全文 »

伯努利数

伯努利数是一个用于解决 nn 次方和的数列。

它的递归定义公式如下:

i=0n(n+1i)Bi=[n=0]        (1.1)\sum_{i=0}^n \binom {n+1} i B_i=[n=0] ~~~~~~~~ (1.1)

阅读全文 »

CF575A Fibonotci

考试的时候写了3.5h , 考后又写了2h 才过掉。

每次修改只会影响两个矩阵,可以暴力计算。

我们知道矩阵乘法有结合律,那么两次修改之间的矩阵可以快速求出乘积。

阅读全文 »

P5437 【XR-2】约定

每一条边被选中的概率: n1n(n1)2=2n\frac{n-1}{\frac{n(n-1)}{2}}=\frac{2}{n}

所以答案为:

2ni=1n1j=i+1n(i+j)k\frac{2}{n} \sum_{i=1}^{n-1} \sum_{j=i+1}^n (i+j)^k

阅读全文 »

P5929 [POI1999]地图

至少有一半不小于 A(k)A(k) , 至少有一半不大于 A(k)A(k)

所以 A(k)A(k) 应该是选出的区域人口的中位数。

为了使误差尽可能小,每次应该取排序后连续的一段区间染相同颜色。

阅读全文 »

SP4060 KPGAME - A game with probability

dp[0/1][i]dp[0/1][i] :有 ii 颗石子 Alice/Bob 为先手,Alice 赢的概率

PP 为 Alice 拿走石子的概率, QQ 为 Bob 拿走石子的概率。

{dp[0][i]=dp[1][i1]P+dp[1][i](1P)dp[1][i]=dp[0][i1]Q+dp[0][i](1Q)\begin{cases}

阅读全文 »